package hebClustering.clusteringAlgorithms;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.IVector;
import hebClustering.vectorSpace.distances.IDistance;

import java.util.Collection;

/**
 * Implementation of the clustering algorithm Hierarchical clustering.
 * 
 *	Every iteration, the algorithm merge the two closest clusters, until K clusters are present. 
 * 
 * 	@see <a href="http://en.wikipedia.org/wiki/Hierarchical_clustering" target="_blank">Hierarchical clustering</a>
 */
public class HierarchicalClustering implements IClusteringAlgorithm{

	private int K;
	private IDistance d;

	public HierarchicalClustering(int K, IDistance d){
		this.K = K;
		this.d = d;
	}

	@Override
	public ClusterSet cluster(Collection<IVector> dataSet) {

		Cluster clusterArray[] = new Cluster[dataSet.size()];
		int index = 0;
		for (IVector v : dataSet){
			Cluster c = new Cluster();
			c.add(v);
			clusterArray[index++] = c;
		}

		int numOfCurrentClusters = dataSet.size();

		Double similarityMatrix[][] = calcSimilarityMatrix(clusterArray);
		
		while (numOfCurrentClusters-- > K)
			mergeTwoClosestClusters(clusterArray,similarityMatrix);		
		
		ClusterSet clusterSet = new ClusterSet();
		for (Cluster c : clusterArray){
			if (c != null)
				clusterSet.add(c);
		}
		return clusterSet;
	}

	private void mergeTwoClosestClusters(Cluster[] clusterArray,Double[][] similarityMatrix) {

		double minDist = Double.MAX_VALUE;
		int minI=-1,minJ=-1;
		for (int i = 0; i < similarityMatrix.length; i++){
			for (int j = 0; j < i; j++){
				if (clusterArray[i] != null && clusterArray[j] != null && similarityMatrix[i][j] < minDist){
					minDist = similarityMatrix[i][j];
					minI = i;
					minJ = j;
				}
			}
		}

		mergeClusters(clusterArray,similarityMatrix,minI,minJ);
	}

	private void mergeClusters(Cluster[] clusterArray, Double[][] similarityMatrix,int minI,int minJ) {

		clusterArray[minI].addAll(clusterArray[minJ]);
		clusterArray[minJ] = null;

		for (int i = 0; i < clusterArray.length; i++){
			if (i != minI && clusterArray[i] != null){
				similarityMatrix[i][minI] = similarityMatrix[minI][i] = Math.min(similarityMatrix[i][minI],similarityMatrix[i][minJ]);
			}
		}

		for (int i = 0; i < clusterArray.length; i++){
			if (i != minJ){
				similarityMatrix[minJ][i] = similarityMatrix[i][minJ] = -1.0;
			}
		}

	}

	private Double[][] calcSimilarityMatrix(Cluster clusterArray[]) {
		Double[][] mat = new Double[clusterArray.length][clusterArray.length];
		for (int i = 0; i < mat.length; i++){
			mat[i][i] = 0.0;
			for (int j = 0; j < i; j++){ 
				mat[i][j] = mat[j][i] = distance(clusterArray[i], clusterArray[j]);
			}
		}
		return mat;
	}


	private double distance(Cluster cluster1, Cluster cluster2) {
		//return d.calc(cluster1.findCentroid(), cluster2.findCentroid());


		double minDist = Double.MAX_VALUE;

		for (IVector v1 : cluster1){
			for (IVector v2 : cluster2){
				double dist = d.calc(v1, v2);
				if (dist < minDist)
					minDist = dist;
			}
		}

		return minDist;
	}


}
